package leetCode.solution;
/**
 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class Solution70 {
	public static void main(String[] args) {

	}

	public int climbStairs(int n) {
		int [] arr = new int[n+1];
		return next(n, arr);
    }
	
	private int next(int n, int [] arr) {
		if(n<=2) return n;
		if(arr[n]>0) return arr[n];
		int result = next(n-1, arr)+next(n-2, arr);
		arr[n]=result;
		return result;
	}
}
